noioj Stupid cat & Doge

noioj
分治

noioj Stupid cat & Doge

题目链接

题解：

一开始我的写法比较无脑。

根据路的弯折形态分类讨论。我们根据路的弯折形态把路分为四类:

img
img
img
img

每一类都由四个子路径组成，我们根据编号范围递归求解相应的子路径，直到找到坐标位置。

如第一类，它的四个子路径，按照路径可以分解以下子问题：

img

其他的也类似这样。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void Rd(ll&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
struct node{
	ll x,y;
}pos1,pos2;
void dfs(node &cur,ll x,ll y,ll len,ll id,ll idl,ll idr,int type){
//	printf("%lld %lld %lld %lld %lld %lld %d\n",x,y,len,id,idl,idr,type);
	if(len==1){
		cur=(node){x,y};
		return;
	}
	ll cnt=(idr-idl+1)/4;
	if(type==1){
		if(id<=cnt+idl-1)dfs(cur,x,y,len/2,id,idl,cnt+idl-1,2);
		else if(id<=cnt*2+idl-1)dfs(cur,x,y+len/2,len/2,id,cnt+idl,cnt*2+idl-1,1);
		else if(id<=cnt*3+idl-1)dfs(cur,x+len/2,y+len/2,len/2,id,cnt*2+idl,cnt*3+idl-1,1);
		else dfs(cur,x+len/2,y,len/2,id,cnt*3+idl,cnt*4+idl-1,4);
	}else if(type==2){
		if(id<=cnt+idl-1)dfs(cur,x,y,len/2,id,idl,cnt+idl-1,1);
		else if(id<=cnt*2+idl-1)dfs(cur,x+len/2,y,len/2,id,cnt+idl,cnt*2+idl-1,2);
		else if(id<=cnt*3+idl-1)dfs(cur,x+len/2,y+len/2,len/2,id,cnt*2+idl,cnt*3+idl-1,2);
		else dfs(cur,x,y+len/2,len/2,id,cnt*3+idl,cnt*4+idl-1,3);
	}else if(type==3){
		if(id<=cnt+idl-1)dfs(cur,x+len/2,y+len/2,len/2,id,idl,cnt+idl-1,4);
		else if(id<=cnt*2+idl-1)dfs(cur,x+len/2,y,len/2,id,cnt+idl,cnt*2+idl-1,3);
		else if(id<=cnt*3+idl-1)dfs(cur,x,y,len/2,id,cnt*2+idl,cnt*3+idl-1,3);
		else dfs(cur,x,y+len/2,len/2,id,cnt*3+idl,cnt*4+idl-1,2);
	}else{
		if(id<=cnt+idl-1)dfs(cur,x+len/2,y+len/2,len/2,id,idl,cnt+idl-1,3);
		else if(id<=cnt*2+idl-1)dfs(cur,x,y+len/2,len/2,id,cnt+idl,cnt*2+idl-1,4);
		else if(id<=cnt*3+idl-1)dfs(cur,x,y,len/2,id,cnt*2+idl,cnt*3+idl-1,4);
		else dfs(cur,x+len/2,y,len/2,id,cnt*3+idl,cnt*4+idl-1,1);
	}
}
ll T,f[35],f2[35];
int main(){
	Rd(T);
	f[0]=f2[0]=1;
	for(int i=1;i<=31;i++)
		f[i]=f[i-1]*2,f2[i]=f2[i-1]*4;
	for(int i=1;i<=T;i++){
		ll n,id1,id2;
		Rd(n),Rd(id1),Rd(id2);
		dfs(pos1,1,1,f[n],id1,1,f2[n],2);
		dfs(pos2,1,1,f[n],id2,1,f2[n],2);
		ll daltx=abs(pos1.x-pos2.x)*10;
		ll dalty=abs(pos1.y-pos2.y)*10;
		long double ans=sqrt((long double)daltx*daltx+(long double)dalty*dalty);
		ll temp=ans;
        cout<<((ans>=temp+0.5)?(temp+1):temp)<<endl;  
	}
	return 0;
}

但有更方便的写法：

不用分成四类路径，而是在递归时，时时将坐标转换。

具体看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
struct node {
    ll x,y;
};
node dfs(ll n,ll x) {
	node p;
    if(n==1)return (node){1,1};
    if(x>n*n/4&&x<=n*n/2){
        p=dfs(n/2,x-n*n/4);
        p.y+=n/2;
    }else if(x>n*n/2&&x<=n*n/4*3) {
        p=dfs(n/2,x-n*n/2);
        p.x+=n/2;
        p.y+=n/2;
    }else if(x>0&&x<=n*n/4) {
        p=dfs(n/2,n*n/4-x+1);
        ll t=n/2-p.x+1;
        p.x=p.y;
        p.y=t;
    }else{
        p=dfs(n/2,n*n-x+1);
        ll t=n/2-p.y+1;
        p.y=p.x;
        p.x=t;
        p.x+=n/2;
    }
    return p;
}
int main() {
    int T,k;
    ll n,id1,id2;
    cin>>T;
    for(int i=1;i<=T;i++) {
        cin>>k>>id1>>id2;
        n=pow(2,k);
        node pos1=dfs(n,id1),pos2=dfs(n,id2);
        long double da=(pos1.x-pos2.x)*(pos1.x-pos2.x);
        long double db=(pos1.y-pos2.y)*(pos1.y-pos2.y);
        long double dis=sqrt((long double)da+db)*10;
        ll ans=dis+0.5;
        cout<<ans<<endl;
    }
    return 0;
}
分享到 评论